/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
    if(!root)return;
    let //res = [],
        cur = root,
        preCur = null,
        first = false,
        p1,
        p2,
        pre = null;

    //morris Traversal
    while (cur){
        if(!cur.left){

            if(preCur && preCur.val>cur.val){
                if(!first){
                    p1 = preCur;
                    first = true;
                }
                p2 = cur;
            }
            preCur = cur;

            cur = cur.right;
        }else{
            pre = cur.left;
            while (pre.right && pre.right!==cur){
                pre = pre.right;
            }
            if(!pre.right){
                pre.right = cur;
                cur = cur.left;
            }else if(pre.right===cur){
                pre.right = null;

                if(preCur && preCur.val>cur.val){
                    if(!first){
                        p1 = preCur;
                        first = true;
                    }
                    p2 = cur;
                }
                preCur = cur;

                cur = cur.right;
            }
        }
    }
    if(p1&&p2&&p1.val){
        let t = p1.val;
        p1.val = p2.val;
        p2.val = t;
    }
};